package club.worldbang.structures.linkedList.doubleLinked;

import club.worldbang.structures.linkedList.ILinkedList;

//带头结点的双链表实现
public class HeadDoubleILinkedList<T> implements ILinkedList<T> {

	protected DNode<T> head; // 不带数据的头结点
	protected DNode<T> tail; // 指向尾部的指针

	public HeadDoubleILinkedList() {
		this.head = this.tail = new DNode<>(); // 初始化头结点
	}

	// 传入一个数组转换成链表
	public HeadDoubleILinkedList(T[] array) {
		this();
		if (array != null && array.length > 0) {
			this.head.next = new DNode<T>(array[0]);
			tail = this.head.next;
			tail.prev = this.head;
			int i = 1;// 记录结点数
			while (i < array.length) {
				tail.next = new DNode<T>(array[i++]);
				tail.next.prev = tail;
				tail = tail.next;
			}
		}
	}

	@Override
	public boolean isEmpty() {
		return head.next == null;
	}

	@Override
	public int length() {
		int length = 0;
		DNode<T> pre = head.next;
		while (pre != null) {
			length++;
			pre = pre.next;
		}
		return length;
	}

	@Override
	public T get(int index) {
		if (index >= 0) {
			int j = 0;
			DNode<T> pre = this.head.next;
			while (pre != null && j < index) {
				j++;
				pre = pre.next;
			}
			if (pre != null) {
				return pre.data;
			}
		}

		return null;
	}

	@Override
	public T set(int index, T data) {
		T old = null;
		if (index >= 0 && data != null) {
			int j = 0;
			DNode<T> pre = this.head.next;
			while (pre != null && j < index) {
				j++;
				pre = pre.next;
			}
			if (pre != null) {
				old = pre.data;
				pre.data = data;// 替换数据
			}
		}
		return old;
	}

	// 插入结点
	@Override
	public boolean add(int index, T data) {
		if (index < 0 || data == null) {
			throw new NullPointerException("index < 0 || data == null");
		}
		int j = 0;
		DNode<T> front = this.head;
		// 查找要插入位置的前一个结点
		while (front.next != null && j < index) {
			j++;
			front = front.next;
		}
		// 创建需要插入的结点信息,前继结点指向front,后继结点指向front.next
		DNode<T> q = new DNode<>(data, front, front.next);
		// 如果front.next != null ，即不是空链表也不是尾部
		if (front.next != null) {
			// 更改front的前继指针为：DNode q
			front.next.prev = q;
		}
		// 更改front的后继指针
		front.next = q;
		// 在尾部插入时，需要注意更新tail的指针指向
		if (front == this.tail) {
			this.tail = q;
		}

		return true;
	}

	// 尾部添加
	@Override
	public boolean add(T data) {
		if (data == null) {
			return false;
		}
		// 尾部添加，创建添加的node信息，前继指针为之前的tail
		DNode<T> q = new DNode<>(data, tail, null);
		// tail的next指向新进的q
		tail.next = q;
		// 最新尾部结点tail指向修改为q
		this.tail = q;
		return true;

	}

	@Override
	public T remove(int index) {
		int length = length();
		T temp = null;
		if (index < 0 || index > length || isEmpty()) {
			return temp;
		}
		DNode<T> p = this.head;
		int j = 0;
		// 查询要删除的结点位置的结点信息
		while(p!=null && j <= index) {
			p = p.next;
			j++;
		}
		if(p.next != null) {
			p.next.prev = p.prev;//删除结点的下一个结点的前一个结点指向改变为删除结点的上一个结点
		}
		p.prev.next = p.next;
		//如果是尾部结点
		if(p == this.tail) {
			this.tail = p.prev;
		}
		temp = p.data;
		return temp;
	}

	//根据data删除结点,无需像单向链表那样去存储要删除结点的前一个结点
	@Override
	public boolean removeAll(T data) {
		boolean isRemove = false;
		if(data == null || isEmpty()) {
			return isRemove;
		}
		//
		DNode<T> p = this.head.next;
		while(p != null) {
			if(p.data.equals(data)) {
				//如果是尾结点，更新尾结点指向
				if(p == this.tail) {
					this.tail = p.prev;
					p.prev = null;
					this.tail.next = null;
				}else {//中间结点，更新前继结点和后继结点的指针指向
					p.prev.next = p.next;
					p.next.prev = p.prev;
				}
				isRemove = true;
				p = p.next;
			}
		}
		return isRemove;
	}

	@Override
	public void clear() {
		this.head.next = null;
		this.tail = this.head;
	}

	@Override
	public boolean contains(T data) {
		if(data == null) {
			return false;
		}
		DNode<T> p = this.head.next;
		while(p!=null) {
			if(p.data.equals(data)) {
				return true;
			}else {
				p = p.next;
			}
		}
		return false;
	}
	@Override
    public String toString() {
        String str="(";
        DNode<T> pre = this.head.next;
        while (pre!=null)
        {
            str += pre.data;
            pre = pre.next;
            if (pre!=null)
                str += ", ";
        }
        return str+")";
    }
}
